home *** CD-ROM | disk | FTP | other *** search
- Path: newsxfer2.itd.umich.edu!caen!usenet
- From: Chris Peikert <cpeikert@kamsc.seds.org>
- Newsgroups: comp.lang.c
- Subject: Re: Tough FACTORIAL math problem...
- Date: Sun, 18 Feb 1996 21:54:02 -0500
- Organization: Kalamazoo Area Math & Science Center
- Message-ID: <3127E64A.6A4F@kamsc.seds.org>
- References: <4fr8be$ass@news.iconn.net> <4g898j$5t@umbc9.umbc.edu>
- NNTP-Posting-Host: @pm137-13.dialip.mich.net
- Mime-Version: 1.0
- Content-Type: text/plain; charset=us-ascii
- Content-Transfer-Encoding: 7bit
- X-Mailer: Mozilla 2.0 (Win95; I)
-
- Jonas J. Schlein wrote:
- >
- > In article <4fr8be$ass@news.iconn.net>, The Crow <thecrow@iconn.net> wrote:
- > |> Here is what I am trying to do, I want to find the last NON-ZERO digit of a
- > |> given factorial. For instance,
- > |>
- > |> 5! = 120
- > |>
- > |> so the last non-zero digit is 2. I want to be able to do this up to 1000.
- > |> Problem is, no matter how huge of a data-type you use, there isn't any way
- > |> for the computer to handle 1000!, it is however possible to find the last
- > |> non-zero digit somehow. One thing I have tried is as I went through
- > |> mulitplying the series of numbers in the factorial (5 * 4 * 3 * 2) I would
- > |> remove all the trailing ZEROS, I got this to work up to 789, but it wont
- > |> work with 1000 and i am not really sure why. If anyone has a clue how I
- > |> can do this let me know.
-
- Funny, this is the exact problem #1 and test case on the USACO
- qualifying round. Seeing as how it's past the deadline for writing the
- programs, here's how I did it:
-
- ---CODE STARTS HERE---
- #include <iostream.h>
-
- int rtDigit(int n) {
- long dig=1;
- for(int i=2; i<=n; i++) { // computing factorial
- dig *= i;
- while(!(dig % 10)) // chop of righthand 0s
- dig /= 10;
- dig %= 1000; // keep last three nonzero digits
- }
- return (dig % 10); // return last digit
- }
-
-
- void main() {
- int n=1;
- while(n) { // input != 0
- cout << "Input:\n";
- cin >> n;
- if(n) {
- cout << "Output:\n";
- cout << rtDigit(n) << "\n"; // return the digit
- }
- }
- }
- ---CODE ENDS HERE---
-
- The critical code portion is this:
-
- dig *= i;
- while(!(dig % 10)) // chop of righthand 0s
- dig /= 10;
- dig %= 1000; // keep last three nonzero digits
-
- in the for loop. It kills all of the righthand 0s, then keeps only the
- three righthand non-zero digits. Worst-case scenario involves
- multiplication of 999*999, which is safe for a long. The reason I kept
- the last _three_ nonzero digits is because the thousands digit of "dig"
- cannot possibly contribute anything to the rightmost nonzero digit if n
- is less than 1000. That, and it works that way :).
-
- But I must ask that, upon presenting the problem, you mention that it's
- for a contest. Otherwise, people who know will think you're cheating.
-
- ----------------------------------------
- Of all the people I know,
- you're one of them.
- Chris Peikert cpeikert@kamsc.seds.org
- http://www.kamsc.k12.mi.us/sp96/cpeikert
-